/*
 * 9.3
 * Given a sorted array of n integers that has been rotated an unknown number of
 * times, give an O(log n) algorithm that finds an element in the array. You may assume
 * that the array was originally sorted in increasing order.
 * EXAMPLE:
 * Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
 * Output: 8 (the index of 5 in the array)
 */
#include <stdio.h>

int search(int *arr, int n, int x)
{
    int left = 0, right = n - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (arr[middle] == x) {
            return middle;
        }
        if (arr[left] <= arr[middle]) {
            /* left part is sorted */
            if (x >= arr[left] && x < arr[middle]) { /* XXX: check with left is necessary. */
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        } else {
            /* right part is sorted */
            if (x > arr[middle+1] && x <= arr[right]) { /* XXX: check with right is necessary. */
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
    }
    return -1;
}

int main()
{
    int arr[] = { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14 };
    int x = 5;
    int i = search(arr, sizeof(arr)/sizeof(arr[0]), x);
    printf("find index of %d is: %d\n", x, i);
    x = 1;
    i = search(arr, sizeof(arr)/sizeof(arr[0]), x);
    printf("find index of %d is: %d\n", x, i);
    x = 25;
    i = search(arr, sizeof(arr)/sizeof(arr[0]), x);
    printf("find index of %d is: %d\n", x, i);
    x = 15;
    i = search(arr, sizeof(arr)/sizeof(arr[0]), x);
    printf("find index of %d is: %d\n", x, i);
    x = 14;
    i = search(arr, sizeof(arr)/sizeof(arr[0]), x);
    printf("find index of %d is: %d\n", x, i);
    x = 0;
    i = search(arr, sizeof(arr)/sizeof(arr[0]), x);
    printf("find index of %d is: %d\n", x, i);
    x = 6;
    i = search(arr, sizeof(arr)/sizeof(arr[0]), x);
    printf("find index of %d is: %d\n", x, i);
    x = 26;
    i = search(arr, sizeof(arr)/sizeof(arr[0]), x);
    printf("find index of %d is: %d\n", x, i);
    return 0;
}
